package com.mlh.binarytree.search;

import com.mlh.binarytree.TreeNode;

/**
 * @author 缪林辉
 * @date 2024/4/3 12:03
 * @DESCRIPTION
 */

// 给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），
// 使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
public class ConvertBST {
    //思路：二叉排序树的中序遍历是升序，我把左右子树递归的顺序调换，就变成了降序
    //利用变量来记录在原树中大于或等于该节点的值之和。 实质上就是降序序列从头到该节点的数值之和
    int pre=0;//记录在原树中大于或等于该节点的值之和
    public TreeNode method1(TreeNode root) {
        recursion(root);
        return root;
    }
    public void recursion(TreeNode node){
        if(node==null){
            return;
        }
        //先递归右子树，再递归左子树
        recursion(node.right);
        pre+= node.val;//相加
        node.val=pre;//将该节点重新赋值
        recursion(node.left);
    }
}
